#数楽 以上の長大に成りすぎた返答連鎖は次のリンク先に続く。https://twitter.com/genkuroki/status/834210961980485632 …

#数楽 どこかで「自由モナドの解説がマックレーン著『圏論の基礎』にない」という発言を見たような気がします。そこでリンクメモ：Barr "Coequalizers and free triples"https://scholar.google.co.jp/scholar?q=Barr+"Coequalizers+and+free+triples" …triple=monad

#数楽 続きTrnkova Adamek Koubek Reiterman "Free algebras, input processes and free monads"https://scholar.google.co.jp/scholar?q=Trnkova+Adamek+Koubek+Reiterman+"Free+algebras,+input+processes+and+free+monads" …"ノイマン級数"のアイデアで自由モナドを作れる

#数楽 続きV Kůrková-Pohlová, V Koubek"When a generalized algebraic category is monadic"https://scholar.google.co.jp/scholar?q="When+a+generalized+algebraic+category+is+monadic" …一つ前のツイートの論文の集合圏版

#数楽 続き。小学校算数では1.111…=1+0.1+0.1^2+0.1^3+…という循環小数の形でノイマン級数が出て来ています。高校数学でノイマン級数は1+a+a^2+…という等比級数の形で出て来る。集合Xで生成される自由モノイド(リスト)は1+X+X^2+…です。

#数楽 続き。函手Fから生成される自由モノイドTは1+F(1+F(1+F(…)))の極限として構成できる。数学を勉強する利点の一つは、関係があると全く考えていなかったこと達について「実は全部同じ話だった！」という気持ちになれることだと思います。算数レベルの話から全部繋がっている。

#数楽 例：函手F:X↦{}=(空集合)が生成する自由モナドTはX→X+FX=X→X+FX=X→…の極限なので X↦Xになる(T=1)。

#数楽 例：函手F:X↦{・}=(一点集合)が生成する自由モナドTはX→X+FX=X+{・}→X+F(X+{・})=X+{・}→…の極限なのでX↦X+{・}=(Xと一点集合の直和)になる。

#数楽 例：恒等函手1:X↦Xが生成する自由モナドTはX→X+1X=X+X→X+1(X+X)=X+X+X→…の極限なので、X↦X+X+X+… (Xの可算直和)になる。すなわちTX=X+X+X+…。このときX+1TX=X+X+X+…=TXとなることは明らか。

#数楽 I=1が生成する自由モナドTはTX=X+IX+IIX+…+I^k X+…と書いて、I^kを識別子のように使えばわかりやすいかも。X+ITX=TXは明らか。φ:X→TYとx∈TXについて、x=I^k x∈I^k Xならばφ^*(t)=I^k f(x)∈I^k Y～続く

#数楽 続き～によって、φ^*:TX→TYを定める。T=1+I+I^2+I^3+…なので、T^2=(1+I+I^2+I^3+…)^2 であり、T^2XはIのべきでgradationが入る。T^2Xの中のI^k XをTXの中のI^k Xに恒等的に移す函数がTのモナド構造μ。

#数楽 函手F:X↦X^2のX^2の要素(x,x')を　 　o　／　＼x　　　　x'のように図示された木(上から下に生えている)とみなすと、Fから生成される自由モナドTについて、TXはXの要素を葉として持つ二分木全体の集合になる(内部ノードはすべて同一のo)。

#数楽 続き。函数φ:X→TYはTXの二分木の葉をYの要素を葉に持つ二分木に対応させる函数とみなせるので、TXの二分木の葉をφによって対応する二分木に置き換える函数φ^*:TX→TYが得られる。

#数楽 続き。Fは集合Xを集合{(a x x')|x,x'∈X}∪{(b x x')|x,x'∈X}に対応させる函手であるとする。(a x x')は次のような木を意味するとする((b x x')についても同様)：　 　a　／　＼x　　　　x'このとき～続く

#数楽 続き～、Fから生成される自由モナドTについて、TXは内部ノードがaまたはbであり、葉がXの要素であるような二分木全体の集合になる。Tのモナド構造は葉の二分木による置換によって自然に定義される。このようなモナドTは有用な一般化を自明にかつ大量に持つが説明略。

#数楽 可換環について説明するときには最初に多項式環について説明することが普通なので、それと同様にモナドについて説明するときにも以上で述べたような易しい自由モナドについて最初に説明しておくと良さそう。モナドTがどうしてT代数を定義するのかも以上の例を知っていれば納得し易いと思う。

#数楽 一般に、ある種の木の全体を考えることはある種の自由モナドを考えることに他ならず、木の内部ノードは葉に作用する演算記号を表わしていると解釈可能。様々な演算記号があれば「代数」に見えて来ます。木の自由モナドがどのような代数を定めるかは定義を知らなくても自動的にわかる。

#数楽 Haskell + Haste で Fourier 級数の可視化 by @lesguillemets on @Qiita http://qiita.com/lesguillemets/items/dbd928237be3e6a1221d …

#数楽 メモT:Set→Setはモナドであるとし、α:TA→AはT代数とする。φ∈TXとf:X→Aに対して、α(Tf(φ))∈Aを対応させる写像TX×A^X→Aが定まる。ゆえに、写像TX→A^A^Xが定まる。X↦A^A^XはT代数Aに値を持つ継続モナド。続く

#数楽 メモ続き。たとえば、FX=X×Xとし、TをFから生成される自由モナドとすると、TXはXの要素を葉とする二分木全体の集合になる。T代数α:TA→Aを与えることは二項演算α:A×A→Aを与えることと同じ。続く

#数楽 続き。そのとき、写像TX×A^X→A, (φ,f)↦α(Tf(φ))は、二分木φ∈TXの中の葉x∈X達を写像f:X→Aによってf(x)∈Aに置換し、各ノードをAの二項演算αと解釈して計算した結果α(Tf(φ))を対応させる写像である。続く

#数楽 続き。すなわち写像TX×A^X→Aは二分木φ∈TXで表現された形式的な式をf:X→Aと二項演算α:A×A→Aで解釈した結果を与える写像になる。その写像はTX→A^A^Xと、モナドTからT代数Aに値を持つ継続モナドへの射を与えている。その射は「解釈」を意味していると思える。

#数楽 続き。TX×A^X→Aは、たとえば、二分木φ=((x,x'),x'')∈TXと写像f=(x↦a,x'↦a',x''↦a'',etc)∈A^Xの組をα(α(a,a'),a'')∈Aに対応させる写像になっている。まさに「解釈」。

#数楽 継続モナドがまだピンと来ていないので話を続ける。継続モナドTの定義はTX=R^R^X=(R^X→R)={X上のR値函数に関するR値汎函数の全体}なので、シュワルツの超函数論と似ています。ただし継続モナドでの汎函数では線型性を考慮しないのですが。続く

#数楽 TXをX上の超函数全体の空間とすると、TTXを考えることは難しいのですが、( )^*:(X→TX)→(TX→TY)の方は考えることができます。すなわち( )^*=∫_Xです。パラメーターxを持つyに関する超函数φ(x,y)∈(X→TY)に対して〜続く

#数楽 継続モナドTX=(R^X→R)の要素は汎函数なので積分の類似物です(積分の一般化がシュワルツの超函数)。積分(もしくはシュワルツの超函数)は函数を数に対抗させる函数(汎函数)の一種です。

#数楽 一方、継続モナドではシュワルツの超函数論とは違って線型性を必ずしも考えません。継続モナドで継続渡しスタイルを実現するときにはそのことを使って定数汎函数(全ての函数を同じ値に対応させる汎函数)が巧妙に使われます(HaskellのcallCC函数)。

#数楽 継続モナドに限らない一般のモナドTについても、φ∈TXとψ∈(X→TY)に対する(φ>>=ψ)∈TYを∫_X dx φ(x)ψ(x,y)と書くのは悪くない記号法かもしれないと思いました。ψ(x,y)のxにφ(x)は代入できないが、「積分」することはできる。続く

#数楽 以上の記号法のもとで、do x←φ y←ψ(x) z←θ(x,y) ρ(x,y,z)を積分記号を使って書くと∫dx φ(x) (∫dy ψ(x,y) (∫dz θ(x,y,z)ρ(x,y,z)))となります。積分記号の意味が大幅に拡張されている。

#数楽 モナドTについて、φ(x)∈TXとψ(x,y)∈(X→TY)に対する(φ>>=ψ)=∫dx φ(x)ψ(x,y)はφの中のxをψに従ってTYの要素(yで作られた何か)に置き換えた(ような)ものを意味しています。この意味での「積分」はそういう置き換えの計算を意味します。

#数楽 積分の意味を大幅に拡張しておけばHaskell的なdo式は逐次「積分」の式だと「思う」ことができるわけです。個人的な意見。「数学的な事柄はどれも似ている」という感覚で眺めることを止めるのは極めて不健全だと思う。機械的な計算も積分に似ている。

#数楽 私の場合には、1001=7×11×13と1027=1001+26より、1027は13では割り切れるが、7と11では割り切れないなと思いました。7,11,13で割った余りの計算では1001をよく使っています。

#数楽 以上では、線形汎函数としての積分(やシュワルツの超函数)→継続モナドTについてTX=R^R^Xは汎函数の集合なので積分で書きたくなる→一般のモナドでも同様という流れで雑談をして来たのですが、継続モナドと一般のモナドの関係については昨晩雑談をしました。続く

#数楽 続き〜、それは以下のリンク先です。https://twitter.com/genkuroki/status/835463647883243521 …RがT代数ならばR値の継続モナドにおけるTの解釈TX→R^R^Xが自然に得られるのでした。だから全てのモナドを継続モナドのようなものと思ってもそう害はないと思いました。続く

#数楽 続き。しかし、そう思うことにしても、継続モナドがピンと来てなければ何の意味もない。そういうわけで今晩の雑談になったわけです。

#数楽 またスレッドを切る。このツイートはリンク先の続き。Applicativeの話を少しするつもり。続くhttps://twitter.com/genkuroki/status/835849829859258370 …

#数楽 以上の長大な返答連鎖は以下のリンク先に続く。こんな早朝に起きてしまった。布団の中から雑談。https://twitter.com/genkuroki/status/836670454609817600 …

#数楽 続き。多変数の函数f:X_1×…×X_n→Yを函手Fで移したとき自然に多変数の函数f':FX_1×…×FX_n→FYが得られたらうれしいのですが、そのためには函数ι:FX_1×…×FX_n→F(X_1×…×X_n)が自然に定まっていれば十分です。続く

#数楽 ι⇒α：id:(X→Y)→(X→Y)からeval:(X→Y)×X→Yが得られ、F((X→Y)×X)→FYが得られ、ι:F(X→Y)×FX→F((X→Y)×X)との合成でF(X→Y)×FX→FYが得られ、α:F(X→Y)→(FX→FY)が得られる。

#数楽 α⇒ι：id:X×Y→X×YからX→(Y→X×Y)が得られ、FX→F(Y→X×Y)が得られ、α:F(Y→X×Y)→(FY→F(X×Y))との合成でFX→(FY→F(X×Y))が得られ、ι:FX×FY→F(X×Y)が得られる。

#数楽 自己函手Tがモナドであるとは、η:X→TXとβ:(X→TY)→(TX→TY)で適当な条件を満たすものが与えられていることなのですが、モナドならばApplicativeであることも簡単にわかります。βからαが作れることの証明に続く。

#数楽 β⇒α：id:(X→Y)→(X→Y)からX→((X→Y)→Y)が得られ、Tの函手性からX→(T(X→Y)→TY)が得られ、T(X→Y)→(X→TY)が得られ、β：(X→TY)→(TX→TY)との合成でα:T(X→Y)→(TX→TY)が得られる。

#数楽 Applicativeなら多変数の函数を多変数の函数に移すので、モナドも多変数の函数を多変数の函数に移してくれるわけです。コードだけを見ると複雑に見えるのですが、Applicativeでやりたいことは多変数の函数を多変数の函数に自然に移すことです。数学的には自明な話。

#数楽 http://d.hatena.ne.jp/kazu-yamamoto/touch/20101211/1292021817 …【Haskellでは〜Applicativeスタイルの一般式は、以下のようになります。f <$> m1 <*> m2 <*> ...】要するに多変数函数f a b …をm1,m2,…の多変数函数に移しているだけ。

#数楽 わけがわからない状態でApplicativeの仕様を眺めるのではなく、「多変数函数を多変数函数にうつすような函手を考える」というポイントを押さえておけば、Applicativeの理解は瞬殺だし、そのような経路で理解しようとしないのは時間の無駄だと思います。

#数楽 以上は全部自明(trivial)な話です。"trivial!"のひとことで瞬殺できる領域が増えれば増えるほど、それ以前には手を出し難かったnon-trivialな領域に手を出し易くなるわけです。だから、trivialと言える領域を増やすことはとても大事。

#数楽 trivialに見える領域を増やすための手段は二つあって、一つ目は理論の定式化を工夫して複雑に見えていた事柄を単純に見えるように工夫すること。二つ目は自分自身の論理的スキルを鍛えて、複雑に見えていた事柄が単純に見えてしまうような力を身につけること。どちらも必須。

#数楽 補足。函手Fの直積に関するstrengthとはX×F(Y)→F(X×Y)のことで、以下のように自然にstrengthが得られます。id:X×Y→X×YからX→(Y→X×Y)が得られX→(F(Y)→F(X×Y))が得られX×F(Y)→F(X×Y)が得られる。

#数楽 続き。直積に関するstrengthを使えばモナドTがlax monoidalであることが以下のようにして示せます。strength X×TY→T(X×Y)からTY→(X→T(X×Y))が得られ、β:(X→T(X×Y))→(TX→T(X×Y))の合成で～続く

#数楽 続き～TY→(TX→T(X×Y))が得られ、ι:TX×TY→T(X×Y)が得られます。モナドは自然に直積に関してlax monoidalです。

#数楽 以上によって、適当な条件のもとで、直積についてmonad⇒applicative⇔lax monoidal⇒functor⇒with strengthであることを示せた。リンク先の質問への答えにもなっていると思う。http://cstheory.stackexchange.com/questions/12412/explaining-applicative-functor-in-categorical-terms-monoidal-functors …

#数楽 ApplicativeなFの話の続きι:FX×FY→F(X×Y)とα=(<*>):F(X→Y)→(FX→FY)の話はしたが、η=pure:X→FXの話をしてなかった。FがApplicativeならば、多変数函数をFでラップされた多変数函数に変換できるのでした。続く

#数楽 続き。そのときに、一部分をFでラップせずに、変換したくなることもあります。たとえば函数f:X×Y×Z→WからXだけはFで包まずにX×FY×FZ→FWという型の函数を作りたいことがある。1変数ならX→YからX→FYを作りたいこともあるでしょう。続く

#数楽 続き。そのような場合には、η=pure:X→FXを使って、FX上の函数をX上の函数にいつでも変換できます。Applicativeを使えばそういうことができるわけです。逆にそういうことを自然にできる仕組みを定義すれば自然にApplicativeになることもわかります。

#数楽 続き。「函手Fで包んだデータを計算するときに、Fで包んだ中身に作用する多変数函数を必要な分だけFで包んだ場合に拡張したい」という自然な要求を実現するための道具がHaskellのApplicativeです。

#数楽 多変数函数を函手で多変数函数に変換したいならばApplicative函手を使い、それを超えることをしたければモナドのような数学的にもっと強い道具を使うことになります。FがApplicativeなら、f:X×Y×Z→Wをf':FX×FY×FZ→FWに変換できる。続く

#数楽 続き。Tがモナドなら、函数の列φ:X→TY, ψ:X×Y→TZ, θ:X×Y×Z→TWから函数TX→TZを作れます。函数の列の前の方で計算した結果を後の方で使える。do x←ξ y←φ(x) z←ψ(x,y) w←θ(x,y,z) return w